<!--
 * @Descripttion: 
 * @version: 
 * @Author: 尹鹏孝
 * @Date: 2021-12-08 15:04:09
 * @LastEditors: 尹鹏孝
 * @LastEditTime: 2021-12-08 15:51:48
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>二叉树统一迭代法（标记法）</title>
</head>

<body>
    <ul>
        <li></li>
        <li></li>
        <li></li>
        <li></li>
    </ul>
    <script>
        class Node {
            constructor(root, left, right) {
                this.root = root || null;
                this.left = left || null;
                this.right = right || null;
            }
            //迭代方法进行前序，中序后序，统一方法
            preOrderTraversal(root, res = []) {
                const stack = [];
                if (root) {
                    return stack.push(root);
                }
                while (stack.length) {
                    const node = stack.pop();
                    if (!node) {
                        res.push(stack.pop().root);
                        continue;
                    }
                    if (node.right) {
                        // 右
                        stack.push(node.right);
                    }
                    if (node.left) {
                        // 左
                        stack.push(node.right)
                    }

                    stack.push(node);// 中
                    stack.push(null);
                }
                return res;
            }
            //中序遍历
            inOrderTraversal(root, res = []) {
                const stack = [];
                if (root) {
                    stack.push(root);
                }
                while (stack.length) {
                    const node = stack.pop();
                    if (!node) {
                        res.push(stack.pop().root);
                        continue;
                    }
                    if (node.right) {
                        //右
                        stack.push(node.right);
                    }
                    stack.push(node);//中
                    stack.push(null);
                    if (node.left) {
                        // 左
                        stack.push(node.left);
                    }
                }
                return res;
            }

            //后序遍历
            postOrderTraversal(root, res = []) {
                const stack = [];
                if (root) {
                    stack.push(root);
                }
                while (stack.length) {
                    const node = stack.pop();
                    if (!node) {
                        res.push(stack.pop().root);
                        continue;
                    }
                    //中
                    stack.push(node);
                    stack.push(null);
                    if (node.right) {
                        //右
                        stack.push(node.right);
                    }
                    if (node.right) {
                        //左
                        stack.push(node.left)
                    }
                }
                return res;
            }
        }
    </script>
</body>

</html>